package com.note.feng.leetcode.algorithms.easy.tree;

public class FourHundredFour {

    /**
     * 404 左叶子之和
     * 给定二叉树的根节点 root ，返回所有左叶子之和。
     *
     * 示例 1：
     *
     * 输入: root = [3,9,20,null,null,15,7]
     * 输出: 24
     * 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
     * 示例 2:
     *
     * 输入: root = [1]
     * 输出: 0
     *
     * 提示:
     *
     * 节点数在 [1, 1000] 范围内
     * -1000 <= Node.val <= 1000
     *  
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/sum-of-left-leaves
     */
    /**
     *解法：深度优先遍历
     * 注意：叶子节点：左子树和右子树都为空的节点
     *
     * @param root
     * @return
     */
    int res = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        return getLeftNodeVal(root);
    }

    private int getLeftNodeVal(TreeNode node){
        if(node != null && node .left != null){
            if(node.left.left == null && node.left.right == null){
                res += node.left.val;
            }else{
                getLeftNodeVal(node.left);
            }
        }
        if(node != null && node.right != null){
            getLeftNodeVal(node.right);
        }
        return res;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
